EVENTO
O Problema do Subgrupo Oculto
Tipo de evento: Seminário de Avaliação - Série A
O Problema do Subgrupo Oculto (PSO) consiste em determinar um subgrupo H de um grupo finito G oculto por uma função que é constante em cada classe lateral de H em G e distinta nas diferentes classes laterais de G. Para ser eficiente, um algoritmo para o PSO tem que ser polilogaritmo na ordem de G. É conhecido na literatura que se o grupo G é abeliano então o PSO em G pode ser resolvido eficientemente por um computador quântico, enquanto, nenhuma solução geral é conhecida para o caso de grupos não-abeianos.Neste seminário apresentaremos o formalismo quântico para o PSO e suas aplicações, como no problema de fatoração de números grandes e o problema de isomorfismo de grafos. Mostraremos as principais técnicas usadas para a solução do problema, os casos onde PSO encontra-se resolvido e o atual estado da arte desta área.
Data Início: 29/04/2009 Hora: 10:00 Data Fim: 29/04/2009 Hora: 12:00
Local: LNCC - Laboratório Nacional de Computação Ciêntifica - Auditorio A
Aluno: Demerson Nunes Gonçalves - Laboratório Nacional de Computação Científica - LNCC
Orientador: Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
Participante Banca Examinadora: Guilherme Augusto de La Rocque Leal - IM-UFRJ - UFRJ Paulo César Marques Vieira - Laboratório Nacional de Computação Científica - LNCC Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
